#include <stdio.h>
#include <stdlib.h>  // 用于 malloc/free 动态分配数组

// 计算欧拉函数 φ(n)：返回 1~n 中与 n 互质的整数个数
int euler_totient(int n) {
    // 1. 初始化数组 phi：phi[i] = i（对应 Python 的 [i for i in range(0, n+1)]）
    int *phi = (int *)malloc((n + 1) * sizeof(int));
    if (phi == NULL) {  // 异常处理：内存分配失败
        printf("内存分配失败！\n");
        exit(1);
    }
    for (int i = 0; i <= n; i++) {
        phi[i] = i;
    }

    // 2. 核心逻辑：遍历每个i，更新其倍数的phi值（phi[j] -= phi[i]）
    for (int i = 1; i <= n; i++) {
        // j从i*2开始（i<<1 等价于 i*2），步长为i，遍历所有i的倍数
        for (int j = i << 1; j <= n; j += i) {
            phi[j] -= phi[i];
        }
    }

    // 3. 保存结果并释放内存（避免内存泄漏）
    int result = phi[n];
    free(phi);
    return result;
}

int main() {
    // 测试用例：与Python一致，计算 φ(10)
    int n = 10;
    printf("%d\n", euler_totient(n));  // 输出：4
    return 0;
}